描述

给定一个长度为n的数组a和一个正整数k，从数组中选择四个数，要求四个数的乘积小于等于k，求方案总数。
数组中可能出现多个值相同的数。
每次选择四个数时，同一个数不能被选择两次，而值相同的两个不同的数可以同时被选。
1 \leq n \leq 10^31≤n≤10
3

1 \leq a[i] \leq 10^6 (1 \leq i \leq n)1≤a[i]≤10
6
(1≤i≤n)
1 \leq k \leq 10^61≤k≤10
6

样例

给定 n = 5, a = [1,1,1,2,2], k = 3, 返回 2 。

解释：
假设方案[i,j,p,q]表示选择的四个数分别为：a[i],a[j],a[p],a[q]。0<= i,j,p,q < n。
则满足条件的方案有：
[0,1,2,3]
[0,1,2,4]
给定 n = 5 ， a = [2,4,9,4,3], k = 300, 返回 4 。

解释：
假设方案[i,j,p,q]表示选择的四个数分别为：a[i],a[j],a[p],a[q]。0<= i,j,p,q < n。
则满足条件的方案有：
[0,1,3,4]
[0,1,2,4]
[0,2,3,4]
[0,1,2,3]

思路

最暴力的方法是遍历全部的i j p q，复杂度是O(n4)，不可取。
如果是两数乘积，这个题目就变得非常简单，对数组排序之后，用前后两个指针遍历。
这个题目根据这个思路就可以变成先固定2个指针i，j，然后变成两数乘积。再加上一些控制条件，变得相对简单一些。

代码

class Solution {
public:
    /**
     * @param n: The length of the array
     * @param a: Known array
     * @param k: The product of the selected four numbers cannot be greater than k
     * @return: The number of legal plan
     */
    long long numofplan(int n, vector<int> &a, int k) {
        // Write your code here
        if (n < 4) return 0;
        long long res = 0;
        sort(a.begin(), a.end());
        int i = 0, j, p,q;
        for (i = 0; i < n; i++) {
            for (j = i+1; j < n; j++) {
                p = j+1;
                q = n-1;
                int temp = k / (a[i]*a[j]);

                if (a[p] * a[p+1] > temp)
                    continue;

                if (a[q] * a[q-1] <= temp) {
                    res += ((q-p+1)*(q-p)/2);
                    continue;
                }
                while (q-p>=1) {
                    if (a[p] * a[q] <= temp) {
                        res += (q-p);
                        p++;
                    }
                    else
                        q--;
                }
            }
        }
        return res;
    }
};

-------------end of filethanks for reading-------------